题目分析

本题是318场周赛的最后一题，小伙伴们不要被题目吓到了，就是一个搜索类的题目，可以用记忆化搜索或者动态规划去求解。小伙伴们试一试。

记忆化搜索

我们先搞清楚一个原则，如果机器人r1 < r2，维修厂f1 < f2，那么r1放在f1，r2放在f2一定是最优解。这个小伙伴们可以自行推算一下可能出现的情况，比较容易。

因此我们需要先将机器人和工厂按照位置进行排序。

新建一个搜索函数DFS，入参为r和f，表示从f个维修厂到最后一个维修场修理从第r个robot到最后一个robot最小的移动距离。

记fn为维修厂的总数，rn为机器人的总数。因此当r = rn时，表示所有的机器人都已经修理好了，返回0即可。当f = fn时，表示维修厂已经没有了，还有机器人没修理，返回无穷大即可。

然后就是遍历机器人，如果第r个机器人不放在第f个维修厂，那么结果是dfs(r, f + 1)。如果第r个机器人放在第f个维修厂，第r + 1个机器人不放在第f个维修厂，结果是dfs(r + 1, f + 1) + cost[r][f]，cost[r][f]是第r个机器人到第f个工厂的距离。一次类推，直到第f个工厂无法维修或者机器人到达上限位置。

总共的状态是nm个，每种要考虑m种可能，算法的时间复杂度为O(nm^2)，空间复杂度为O(mn)，其中n为工厂数，m为机器人数。

class Solution {
    private long[][] mem;

    private int rn;

    private int fn;

    private List<Integer> robot;

    private int[][] factory;

    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        robot.sort(Comparator.comparingInt(o -> o));
        Arrays.sort(factory, Comparator.comparingInt(o -> o[0]));
        rn = robot.size();
        fn = factory.length;
        mem = new long[rn][fn];
        this.robot = robot;
        this.factory = factory
        return dfs(0, 0);
    }

    private long dfs(int r, int f) {
        if (r == rn) {
            return 0;
        }
        if (f == fn) {
            return Long.MAX_VALUE >> 1;
        }
        if (mem[r][f] != 0) {
            return mem[r][f];
        }
        mem[r][f] = dfs(r, f + 1);
        long cost = 0;
        for (int k = r; k < Math.min(r + factory[f][1], rn); k++) {
            cost += Math.abs(factory[f][0] - robot.get(k));
            mem[r][f] = Math.min(mem[r][f], dfs(k + 1, f + 1) + cost);
        }
        return mem[r][f];
    }
}

动态规划

我们发现记忆化搜索的格式类似于动态规划，这个mem数组也是根据状态转移计算出来的。

这个题目是否也可以用动态规划来求解呢？

这里记dp[i][j]表示从前i个工厂修理前j个机器人需要的移动距离。注意和记忆化不一样，记忆化是从i到最后一个，这里是从第一个到i。

那么有

$$ dp[i][j] = min(dp[i - 1][k] + sum[i][k])，k >= 0 && j - f[i][1] <= k $$

其中sum[i][k]是从第k个机器人到第j个机器人，到第i个维修厂的总距离

算法的时间复杂度为O(nm^2)，空间复杂度为O(mn)，其中n为工厂数，m为机器人数。

class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        robot.sort(Comparator.comparingInt(o -> o));
        Arrays.sort(factory, Comparator.comparingInt(o -> o[0]));
        int rn = robot.size();
        int fn = factory.length;
        long[][] dp = new long[fn][rn];
        Arrays.fill(dp[0], Long.MAX_VALUE >> 1);
        dp[0][0] = factory[0][1] == 0 ? Long.MAX_VALUE >> 1 : Math.abs(factory[0][0] - robot.get(0));
        for (int j = 1; j < Math.min(rn, factory[0][1]); j++) {
            dp[0][j] = dp[0][j - 1] + Math.abs(factory[0][0] - robot.get(j));
        }
        for (int i = 1; i < fn; i++) {
            for (int j = 0; j < rn; j++) {
                long cost = 0;
                dp[i][j] = dp[i - 1][j];
                for (int k = j; k >= Math.max(0, j - factory[i][1] + 1); k--) {
                    cost += Math.abs(factory[i][0] - robot.get(k));
                    dp[i][j] = Math.min(dp[i][j], (k == 0 ? 0 : dp[i - 1][k - 1]) + cost);
                }
            }
        }
        return dp[fn - 1][rn - 1];
    }
}

可以对上面这个代码进行优化，创建n + 1行，n + 1列，则不需要特殊处理

public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
    robot.sort(Comparator.comparingInt(o -> o));
    Arrays.sort(factory, Comparator.comparingInt(o -> o[0]));
    int rn = robot.size();
    int fn = factory.length;
    long[][] dp = new long[fn + 1][rn + 1];
    Arrays.fill(dp[0], Long.MAX_VALUE >> 1);
    dp[0][0] = 0;
    for (int i = 1; i <= fn; i++) {
        for (int j = 1; j <= rn; j++) {
            long cost = 0;
            dp[i][j] = dp[i - 1][j];
            for (int k = j; k >= Math.max(1, j - factory[i - 1][1] + 1); k--) {
                cost += Math.abs(factory[i - 1][0] - robot.get(k - 1));
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][k - 1] + cost);
            }
        }
    }
    return dp[fn][rn];
}

看到上面这个状态转移方程，又可以联想到01背包，可以从后向前遍历，省去一维空间。

下面就是最优化版的动态规划写法，算法的时间复杂度为O(nm^2)，空间复杂度为O(m)，其中n为工厂数，m为机器人数。

class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        robot.sort(Comparator.comparingInt(o -> o));
        Arrays.sort(factory, Comparator.comparingInt(o -> o[0]));
        int rn = robot.size();
        int fn = factory.length;
        long[] dp = new long[rn + 1];
        Arrays.fill(dp, Long.MAX_VALUE >> 1);
        dp[0] = 0;
        for (int[] ints : factory) {
            for (int j = rn; j >= 1; j--) {
                long cost = 0;
                for (int k = j; k >= Math.max(1, j - ints[1] + 1); k--) {
                    cost += Math.abs(ints[0] - robot.get(k - 1));
                    dp[j] = Math.min(dp[j], dp[k - 1] + cost);
                }
            }
        }
        return dp[rn];
    }
}

刷题总结

动态规划和记忆化搜索本质是非常相似的，两者各有优劣，记忆化搜索的优势在于思路清晰，写法简单。但是劣势是时间复杂度较高，多了栈的调用。动态规划的优势在于可以用数据结构优化转移方程，但是写法较为困难，能写出动态规划版本，也是很不容易的。